package 链表和树.二叉树;
//Java：将有序数组转换为二叉搜索树
public class ConvertSortedArrayToBinarySearchTree{
    public static void main(String[] args) {
        Solution solution = new ConvertSortedArrayToBinarySearchTree().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
//    public class TreeNode {
//        int val;
//        TreeNode left;
//        TreeNode right;
//        TreeNode() {}
//        TreeNode(int val) { this.val = val; }
//        TreeNode(int val, TreeNode left, TreeNode right) {
//            this.val = val;
//            this.left = left;
//            this.right = right;
//        }
//    }
class Solution {
       //什么是高度平衡二叉搜索树？
       //二叉搜索树（BST）：对于任意节点，左子树所有节点的值都小于该节点的值，右子树所有节点的值都大于该节点的值
       //高度平衡：每个节点的左右子树的高度差的绝对值不超过1
    public TreeNode sortedArrayToBST(int[] nums) {
        return dfs(nums, 0, nums.length);
    }

    //区间定义方式
    //在代码中，使用的是左闭右开区间 [left, right) 的方式来表示子数组范围：
    //left：包含在区间内的第一个元素索引
    //right：不包含在区间内的第一个元素索引（即区间的结束位置）
    //这种区间定义方式有以下特点：
    //区间 [left, right) 包含的元素个数为 right - left方便计算中间节点
    //当 left == right 时，区间为空
    //一个区间 [left, right) 可以被分割为 [left, mid) 和 [mid, right)
    private TreeNode dfs(int[] nums, int left, int right) {
            if(left == right){
                return null;
            }
// // 取中间位置作为根节点，确保左右子树节点数量差不超过1
//        int mid = left + (right - left) / 2;
            int mid = (right+left) >>> 1;//mid = (0 + 5) >>> 1 = 2 (无符号右移一位)
        TreeNode root = new TreeNode(nums[mid]);
        // 构建左子树：使用区间 [left, mid)
        root.left = dfs(nums, left, mid);
        // 构建右子树：使用区间 [mid+1, right)
        root.right = dfs(nums, mid+1, right);

        return root;//返回平衡的二叉搜索树的根节点
    }

}
//leetcode submit region end(Prohibit modification and deletion)

}